package com.github.hgkmail.hello.leetcode101.pointer.tree;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;
import com.github.hgkmail.hello.leetcode101.base.TreeNode;

//翻转二叉树
//homebrew的作者Max Howell大神面试Google没写出的面试题，居然是easy题。。。
//树的dfs是[从下到上]的！！遍历顺序（4层）：空节点 -> 叶子节点 -> 内部节点 -> 根节点
public class LC226InvertBinaryTree {
    public TreeNode dfs(TreeNode root) {
        if (root==null) {
            return root;
        }
        TreeNode left=dfs(root.left);
        TreeNode right=dfs(root.right);
        root.left=right;
        root.right=left;
        return root;
    }
    public TreeNode invertTree(TreeNode root) {
        return dfs(root);
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1, null, null);
        TreeNode b = new TreeNode(3, null, null);
        TreeNode c = new TreeNode(2, a, b);
        CommonUtil.printBinaryTree(c);
        CommonUtil.printBinaryTree(new LC226InvertBinaryTree().invertTree(c));
    }
}
